package zuochengyun;

import java.util.Arrays;

public class MinImpossibleSum {

	/**
	 * 给定一个正整数数组arr，如果有数不可以被某一个子集相加得到，就是最小不可组成和
	 * 求最小不可组成和
	 * @param arr
	 * @return
	 */
	public int unformedSum(int[] arr){
		if(arr == null || arr.length <= 0){
			return 1;
		}
		int sum = 0;
		int min = Integer.MAX_VALUE;
		for (int i = 0; i < arr.length; i++) {
			sum += arr[i];
			min = Math.min(min, arr[i]);
		}
		
		//dp的意思是dp[i]为true，表示i这个累加和可以组成
		boolean[] dp = new boolean[sum + 1];
		dp[0] = true;
		for (int i = 0; i < dp.length; i++) {
			//如果arr[0...i]这个范围能组成k，那么arr[0...i+1]能组成k + arr[i + 1]
			//此过程是从arr[0...i - 1] 更新到arr[0...i]的过程
			for(int j = sum; j >= arr[i]; j--){
				dp[j] = dp[j - arr[i]] ? true : dp[j];
			}
		}
		//如果有某个数不能组成，直接返回
		for (int i = min; i <= sum; i++) {
			if(!dp[i]){
				return i;
			}
		}
		//如果都可以组成，那么就返回所有的和加1
		return sum + 1;
	}
	
	//如果我们已知一定有1这个数呢，我们可以先排序，然后从左到右计算每个位置的i的range，range代表计算到arr[i]时
	//[1...range]区间内的所有正数都可以被arr[0...i-1]的某一个子集加出来
	//如果arr[i] > range + 1,由于是有序的，之后的数字不会有比arr[i]小的，所以直接返回range+1
	//如果arr[i] <= range + 1, 说明[1...range + arr[i]]都可以由arr[0...i]的一个子集加出来
	public int unformedSum2(int[] arr){
		if(arr == null || arr.length <= 0){
			return 0;
		}
		Arrays.sort(arr);
		int range = 0;
		for(int i = 0; i < arr.length; i++){
			if(arr[i] > range + 1){
				return range + 1;
			}else{
				range += arr[i]; 
			}
		}
		return range +1;
	}
}
